8.9 Ejemplo de árbol AVL en C  

No ha demasiado que añadir, construiremos los ejemplos de árboles AVL basándonos en los ejemplos que hicimos para árboles binarios de búsqueda.

Sólo tenemos que añadir cinco nuevas funciones: una para equilibrar el árbol, y cuatro para las cuatro posibles rotaciones.

Además, modificaremos ligeramente las funciones de inserción y borrado para que se equilibre el árbol automáticamente después de cada inserción o borrado.

En la estructura de nodo para árbol AVL añadiremos un puntero al nodo padre y un valor entero para almacenar el factor de equilibrio.

Cuando se inserten nuevos nodos hay que ajustar los valores de los nuevos miembros de nodo: FE y padre. Seguidamente, llamaremos a la función "Equilibrar", salvo que el nodo insertado sea el raíz, ya que en ese caso no es necesario, evidentemente.

El procedimiento de equilibrar consiste en la implementación del algoritmo que vimos en el punto anterior:

/* Equilibrar árbol AVL partiendo de un nodo*/
void Equilibrar(Arbol *a, pNodo nodo, int rama, int nuevo) {
   int salir = FALSE;

   /* Recorrer camino inverso actualizando valores de FE: */
   while(nodo && !salir) {
      if(nuevo)
         if(rama == IZQUIERDO) nodo->FE--; /* Depende de si añadimos ... */
         else                  nodo->FE++;
      else
         if(rama == IZQUIERDO) nodo->FE++; /* ... o borramos */
         else                  nodo->FE--;
      if(nodo->FE == 0) salir = TRUE; /* La altura de las rama que
                                         empieza en nodo no ha variado,
                                         salir de Equilibrar */
      else if(nodo->FE == -2) { /* Rotar a derechas y salir: */
         if(nodo->izquierdo->FE == 1) RDD(a, nodo); /* Rotación doble  */
         else RSD(a, nodo);                         /* Rotación simple */
         salir = TRUE;
      }
      else if(nodo->FE == 2) {  /* Rotar a izquierdas y salir: */
         if(nodo->derecho->FE == -1) RDI(a, nodo); /* Rotación doble  */
         else RSI(a, nodo);                        /* Rotación simple */
         salir = TRUE;
      }
      if(nodo->padre)
         if(nodo->padre->derecho == nodo) rama = DERECHO; else rama = IZQUIERDO;
      nodo = nodo->padre; /* Calcular FE, siguiente nodo del camino. */
   }
}

Las funciones para rotar son también sencillas, por ejemplo, la rotación simple a la derecha:

/* Rotación simple a derechas */
void RSD(Arbol *a, pNodo nodo) {
   pNodo Padre = nodo->padre;
   pNodo P = nodo;
   pNodo Q = P->izquierdo;
   pNodo B = Q->derecho;

   if(Padre)
     if(Padre->derecho == P) Padre->derecho = Q;
     else Padre->izquierdo = Q;
   else *a = Q;

   /* Reconstruir árbol: */
   P->izquierdo = B;
   Q->derecho = P;

   /* Reasignar padres: */
   P->padre = Q;
   if(B) B->padre = P;
   Q->padre = Padre;

   /* Ajustar valores de FE: */
   P->FE = 0;
   Q->FE = 0;
}

Y la rotación doble a la derecha:

/* Rotación doble a derechas */
void RDD(Arbol *raíz, Arbol nodo) {
   pNodo Padre = nodo->padre;
   pNodo P = nodo;
   pNodo Q = P->izquierdo;
   pNodo R = Q->derecho;
   pNodo B = R->izquierdo;
   pNodo C = R->derecho;

   if(Padre)
     if(Padre->derecho == nodo) Padre->derecho = R;
     else Padre->izquierdo = R;
   else *raíz = R;

   /* Reconstruir árbol: */
   Q->derecho = B;
   P->izquierdo = C;
   R->izquierdo = Q;
   R->derecho = P;

   /* Reasignar padres: */
   R->padre = Padre;
   P->padre = Q->padre = R;
   if(B) B->padre = Q;
   if(C) C->padre = P;

   /* Ajustar valores de FE: */
   switch(R->FE) {
      case -1: Q->FE = 0; P->FE = 1; break;
      case 0:  Q->FE = 0; P->FE = 0; break;
      case 1:  Q->FE = -1; P->FE = 0; break;
   }
   R->FE = 0;
}

8.10 Ejemplo de árbol AVL en C++  

Usando clases el ejemplo también está basado en el que hicimos para árboles binarios de búsqueda, añadiendo las cinco funciones anteriores: Equilibrar, RSD, RSI, RDD y RDI. Además de las modificaciones en Insertar y Borrar.

8.11 Ejemplo de árbol AVL en C++ con plantillas  

Usando plantillas no hay más que generalizar el ejemplo de clases, cambiando en tipo de dato a almacenar por el parámetro de la plantilla.

Ficheros con los códigos fuente: